This paper settles the computational complexity of model checking of severalextensions of the monadic second order (MSO) logic on two classes of graphs:graphs of bounded treewidth and graphs of bounded neighborhood diversity. Aclassical theorem of Courcelle states that any graph property definable in MSOis decidable in linear time on graphs of bounded treewidth. Algorithmicmetatheorems like Courcelle's serve to generalize known positive results onvarious graph classes. We explore and extend three previously studied MSOextensions: global and local cardinality constraints (CardMSO and MSO-LCC) andoptimizing a fair objective function (fairMSO). First, we show how thesefragments relate to each other in expressive power and highlight their(non)linearity. On the side of neighborhood diversity, we show that combiningthe linear variants of local and global cardinality constraints is possiblewhile keeping the linear runtime but removing linearity of either makes thisimpossible, and we provide a polynomial time algorithm for the hard case.Furthemore, we show that even the combination of the two most powerfulfragments is solvable in polynomial time on graphs of bounded treewidth.
展开▼
